package org.thewares.collection.baseline;
import org.thewares.collection.Deque;
import org.thewares.collection.ReverseDeque;
object Deck {
      
      val empty:Deque[Nothing] with Seq[Nothing]=EmptyDeck;

      // the rest of the object is private 

      private sealed abstract class Deck[+A] extends Deque[A] with Seq[A]{

	    def apply(n: Int): A;
	    
	    def elements: Iterator[A];
	    def reverseElements: Iterator[A];
	    def reverseDeque=ReverseDeque(this);
	    def isEmpty: Boolean;
	    def length:Int;

	    def push[B >: A](elem: B):Deck[B];
	    def peek:A;
	    def pop:Deck[A];
	    
	    def unshift[B >: A](elem: B):Deck[B];
	    def head: A;
	    def tail: Deck[A];

	    override def equals(o: Any): Boolean={
		  o match {
			case d:Deck[_] => {
			      length==d.length && elements.zip(d.elements).forall{case (a,b) => a==b};
			}
			case _ => false;
		  }
	    }
	    override def hashCode(): Int={
		  (0 /: elements){case (i,a) => i ^ a.hashCode}
	    }

	    def dequeue: (A, Deck[A])=(head,tail);
	    def ::[B >: A](elem: B):Deck[B]= unshift(elem);
	    def shift: Deck[A]=tail;    
	    def enqueue[B >: A](elem: B):Deck[B]=push(elem);
	    def +[B >: A](elem: B) = push(elem);
	    def peekPop: (A, Deck[A])=(peek,pop);

	    def nodes:Int;
	    def depth:Int;
	    def state:String;
 
	    /* throws no errors if array is big enough.
	     * pre: array is big enouhg
	     */
	    def readInto[B >:A](arr:Array[B],arrayOffset:Int,dequeOffset:Int,count:Int):Int;

	    def ++[B >: A](s:Seq[B]): Deck[B] = {
		  (s) match {
			case that:Deck[B] => this ::: that;
			case s => { 
			      throw new Error("yikes");
			      val thisB:Deck[B]=this;
			      (thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    }

	    protected final def fastMake[B](count:Int,iter:Iterator[B]):(Int,Iterator[Deck[B]])={

		  def simpleMake[T](count:Int,iter:Iterator[T]):ArrayDeck[T]={
			val arr=new Array[T](count);
			iter.readInto(arr,0,count);
			ArrayDeck(arr);
		  }
		  if (count <= SIZE){
			(1,Iterator.single(simpleMake(count,iter)));
		  } else {
			val returnCount=(count-1)/SIZE + 1;
			// two decks may not be full; together they have this many elements
			val leftOver= count - ((returnCount-2)*SIZE);
			val firstRemainder=leftOver/2;
			val secondRemainder=leftOver-firstRemainder;
			val lastIndex=returnCount+1;
			val ret=new Iterator[Deck[B]] {
			      var i=0;
			      def hasNext=i<returnCount;
			      def next={			    
				    i += 1;
				    if (i==1) {
					  simpleMake(firstRemainder,iter);
				    } else if (i==returnCount) {
					  simpleMake(secondRemainder,iter);
				    } else {
					  simpleMake(SIZE,iter);
				    }
			      }
			}
			( returnCount, ret );
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B];
      }


      
      private val SIZE=32;
      val S2=SIZE*SIZE;


      private case object EmptyDeck extends Deck[Nothing] {
	    def apply(n:Int):Nothing=error("element "+n+" is not in EmptyDeck"); 
	    def elements=Iterator.empty;
	    def reverseElements=Iterator.empty;
	    override def isEmpty=true;
	    def length=0;
	    
	    def push[B](elem: B):Deck[B]=new SingletonDeck(elem)
	    def peek:Nothing=error("EmptyDeck has no elements"); 
	    def pop:Deck[Nothing]=error("EmptyDeck has no elements"); 
	    
	    def unshift[B](elem: B):Deck[B]=new SingletonDeck(elem);
	    def head: Nothing=error("EmptyDeck has no elements"); 
	    def tail: Deck[Nothing]=error("EmptyDeck has no elements"); 
	    
	    def readInto[B](arr:Array[B],arrayOffset:Int,dequeOffset:Int,count:Int):Int=0;
			

	    def :::[B](that:Deque[B]): Deck[B] = {
		  that match{
			case other:Deck[B] =>{
			      other
			}
			case _ => { // not optimized
			      throw new Error("yikes");
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

	    override val hashCode=0;
	    override def equals(other:Any)= other match{
		  case ed:Deck[_] => ed.length==0;
		  case _ => false;
	    }

	    def nodes=0;
	    def depth=0;
	    def state="0";
      }

      
      private final case class SingletonDeck[+A](a:A) extends Deck[A] {
	    def apply(n:Int):A= if (n==0) {a} else error("element "+n+" is not in SingletonDeck");  
	    def length=1;
	    def elements=Iterator.single(a);
	    def reverseElements=Iterator.single(a);
	    override def isEmpty=false;
	    
	    def push[B >: A](elem: B):Deck[B]={
		  PairDeck(a,elem);
	    }
	    def peek:A= a;
	    def pop:Deck[A]={
		  EmptyDeck
	    }	    
	    def unshift[B >: A](elem: B):Deck[B]={
		  PairDeck(elem,a);
	    }
	    def head: A=a;
	    def tail: Deck[A]={
		  EmptyDeck;
	    }	    
	    def nodes=1;
	    def depth=1;
	    def state="1";

	    def readInto[B >:A](arr:Array[B],arrayOffset:Int,dequeOffset:Int,count:Int)={
		  if (dequeOffset==0 && count>0){
			arr(arrayOffset)=a;
			1;
		  } else {
			0;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match {
			case other:Deck[B] =>
			      other + a;
			case _ => {
			      throw new Error("yikes");
			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}

		  }
	    }
      }

      private object PairDeck{
	    def apply[A](a:A,b:A)={
		  val ret=new Array[A](2);
		  ret(0)=a;
		  ret(1)=b;
		  ArrayDeck(ret);
	    }
      }

      private final case class ArrayDeck[+A](a :RandomAccessSeq[A]) extends Deck[A] {   
	    
	    def apply(n:Int):A=a(n);
	    final def length=a.length;
	    def elements=a.elements;
	    // this is nonoptimal, but be careful not to touch this.a.
	    def reverseElements=a.toList.reverse.elements;
	    override final def isEmpty=false;
	    def readInto[B >:A](arr:Array[B],arrayOffset:Int,dequeOffset:Int,count:Int)={
		  val avail=length-dequeOffset;

		  if (avail<=0){
			0
		  } else {
			val ret=if (count<avail) count else avail;
			Array.copy(a,dequeOffset,arr,arrayOffset,ret);
			ret
		  }
	    }
	    def push[B >: A](elem: B):Deck[B]={
		  if (length>=SIZE){
			new DoubleDeck(this,new SingletonDeck(elem)); //this is cheap but does it build up potential?  No.  The single is top level.
		  } else {
			val ret=new Array[B](length+1);
			Array.copy(a,0,ret,0,length);
			ret(length)=elem;
			new ArrayDeck[B](ret);
		  }
	    }
	    def peek:A= a(length-1);
	    def pop:Deck[A]={
		  
		  if (length <= 2){
			if (length==2){
			      new SingletonDeck(a(0));
			} else {
			      EmptyDeck;
			}
		  } else {
			val ret=new Array[A](length-1);
			Array.copy(a,0,ret,0,length-1);
			new ArrayDeck[A](ret);
		  }
	    }	    
	    def unshift[B >: A](elem: B):Deck[B]={
		  if (length >= SIZE){
			new DoubleDeck(new SingletonDeck(elem),this); //k
		  } else {
			val ret=new Array[B](length+1);
			Array.copy(a,0,ret,1,length);
			ret(0)=elem;
			new ArrayDeck[B](ret);
		  }
	    }
	    def head: A=a(0);
	    def tail: Deck[A]={
		  if (length==2){
			new SingletonDeck(a(1));
		  } else {
			val ret=new Array[A](length-1);
			Array.copy(a,1,ret,0,length-1);
			new ArrayDeck[A](ret);
		  }
	    }	    
	    def nodes=1;
	    def depth=1;
	    def state=if (length>=SIZE) "A" else "a";
	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case EmptyDeck => this;
			case SingletonDeck(x) => x :: this;
			case other:ArrayDeck[B] => {
			      val newLength=other.length+length;
			      if (newLength<=SIZE){
				    val ret=new Array[B](newLength);
				    other.readInto(ret,0,0,other.length);
				    this.readInto(ret,other.length,0,a.length);
				    ArrayDeck(ret);
			      } else {
				    DoubleDeck(other,this);
			      }
			}
			case other:Deck[B] => // double or triple
			      (other /: this){(d,e) => d.push(e)}
			case _:Deque[B] => { // not optimized
			      throw new Error("yikes");
			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    } // end :::
      }



      private final case class DoubleDeck[+A](front:Deck[A],back:Deck[A]) extends Deck[A] {
	    
	    def apply(n: Int): A={
		  if (n<front.length){
			front.apply(n);
		  } else {
			back.apply(n-front.length);
		  }
	    }
	    
	    def elements: Iterator[A]= front.elements ++ back.elements;
	    def reverseElements: Iterator[A]= back.reverseElements ++ front.reverseElements;
	    override def isEmpty: Boolean= false;
	    def length:Int=front.length + back.length;

	    def readInto[B >:A](arr:Array[B],arrayOffset:Int,dequeOffset:Int,count:Int)={
		  val available=front.length-dequeOffset;
		  val frontCount={
			if (available <= 0){
			      0
			} else {
			      val ret= if (available<count)available else count;
			      front.readInto(arr,arrayOffset,dequeOffset,ret);
			      ret
			}
		  }
		  back.readInto(arr,arrayOffset+frontCount,
				 dequeOffset-front.length,count-frontCount)+frontCount;

	    }	    


	    def push[B >: A](elem: B):Deck[B]={
		  if (back.length==SIZE){
			new TripleDeck(length+1,front,new SingletonDeck(back),new SingletonDeck(elem)); //k
		  } else {
			new DoubleDeck(front,back.push(elem)); //k
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={ 
		  val postpop=back.pop;
		  if (postpop.isEmpty){
			front;
		  } else {
			new DoubleDeck(front,postpop);
		  }
	    }
	    def unshift[B >: A](elem: B):Deck[B]={
		  if (front.length==SIZE){
			new TripleDeck(length+1,new SingletonDeck(elem),new SingletonDeck(front),back); //k
		  } else {
			new DoubleDeck(front.unshift(elem),back); //k
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val posttail=front.tail;
		  if (posttail.isEmpty){
			back;
		  } else {
			new DoubleDeck(posttail,back); //k
		  }
	    }

	    def nodes=1+front.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  1+ (if (fd>bd) fd else bd)
	    }
	    def state="["+front.state+","+back.state+"]";
	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case EmptyDeck => this;
			case SingletonDeck(a) => a :: this;
			case other:ArrayDeck[B] => {
			      val totalLength=other.length+this.length;
			      val (count,iter)=fastMake(totalLength,other.elements ++ 
							this.elements);
			      count  match {
				    case 1 => iter.next;
				    case 2 => DoubleDeck(iter.next,iter.next);
				    case 3 => new TripleDeck(totalLength,
							     iter.next,
							     SingletonDeck(iter.next),
							     iter.next);
				    case 4 => new TripleDeck(totalLength,
							     iter.next,
							     PairDeck(iter.next,iter.next),
							     iter.next);
			      }
			}
			case other:DoubleDeck[B] => {
			      val totalLength=other.length+this.length;
			      val (count,iter)=fastMake(totalLength,other.elements ++ 
							this.elements);
			      count  match {
				    case 1 => iter.next;
				    case 2 => DoubleDeck(iter.next,iter.next);
				    case 3 => new TripleDeck(totalLength,
							     iter.next,
							     SingletonDeck(iter.next),
							     iter.next);
				    case 4 => new TripleDeck(totalLength,
							     iter.next,
							     PairDeck(iter.next,iter.next),
							     iter.next);
			      }
			}
			case TripleDeck(n,a,b,c) =>
			      TripleDeck(n+length,a,b.push(c).push(front),back);
			case _ => { // not optimized
			      throw new Error("yikes:  "+that.getClass); // shouldn't be called yet. fixme			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    } // end :::
      }

      // non of these subdeques are empty
      private final case class TripleDeck[+A](N:Int,front:Deck[A],up:Deck[Deck[A]],back:Deck[A]) extends Deck[A] {
	    
	    // slow.
	    def apply(n: Int): A= elements.drop(n).next();
	    
	    // does Iterator.flatten make them less lazy?  Its best if they are not wasting memory.
	    def elements: Iterator[A]= front.elements ++ Iterator.flatten(up.map(_.elements).elements) ++ back.elements;
	    // this looks buggy
	    def reverseElements: Iterator[A]= {back.reverseElements ++ 
					       Iterator.flatten(up.reverseElements.map(_.reverseElements))++
					       front.reverseElements;}
	    override def isEmpty: Boolean= false;
	    def length:Int=N;
	    
	    def push[B >: A](elem: B):Deck[B]={
		  if (back.length==SIZE){
			new TripleDeck(N+1,front,up.push(back),new SingletonDeck(elem));
		  } else {
			new TripleDeck(N+1,front,up,back.push(elem));
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={
		  val postpop=back.pop;
		  if (postpop.isEmpty){
			val uppop=up.pop;
			if (uppop.isEmpty){
			      new DoubleDeck(front,up.peek); 
			} else {
			      new TripleDeck(N-1,front, uppop, up.peek); 
			}
		  } else {
			new TripleDeck(N-1,front,up,postpop); 
		  }
	    }
	    
	    def unshift[B >: A](elem: B):Deck[B]={
		  if (front.length==SIZE){
			new TripleDeck(N+1,new SingletonDeck(elem),up.unshift(front),back);
		  } else {
			new TripleDeck(N+1,front.unshift(elem),up,back);
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val fronttail=front.tail;
		  if (fronttail.isEmpty){
			val uptail=up.tail;
			if (uptail.isEmpty){
			      new DoubleDeck(up.head,back)
			} else {
			      new TripleDeck(N-1,up.head,uptail,back);
			}
		  } else {
			new TripleDeck(N-1,fronttail,up,back);
		  }
	    }
	    def nodes=1+front.nodes+up.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  val mfb=if (fd>bd) fd else bd;
		  val ud=up.depth;
		  1+ (if (ud>mfb) ud else mfb);
	    }
	    def state="("+front.state+","+up.state+","+back.state+")";

	    /* this is less effiecnt; is it ever called? */
	    def readInto[B >:A](arr:Array[B],arrayOffset:Int,dequeOffset:Int,count:Int)={
		  // fixme: preconditions?  check params?  calling shady readIbto
		  elements.drop(dequeOffset).take(count).readInto(arr,arrayOffset);
		  count;
	    }	    



	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case EmptyDeck => this;
			case SingletonDeck(a) => a :: this;
			case ArrayDeck(x) => {
			      val tb:Deck[B]=this;
			      (tb /: x.reverse){(d,e) => e::d}
			} 
			case DoubleDeck(a,b) =>
			      // fixme, can push junk
			      TripleDeck(N+that.length,a, b :: front :: up, back);
			case TripleDeck(n,a,b,c) =>
			      TripleDeck(n+N,a,(b push c) ::: (front::up),back);
			case that:Deque[B] => { // not optimized
			      throw new Error("yikes:  "+that.getClass); // shouldn't be called yet. fixme
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

      }// end TripleDeck

}
